1. Field of the Invention
The present invention relates generally to the field of information security systems, and more specifically to receipts that are binding but not revealing.
2. Description of Prior Art
Election systems generally, as an application example without limitation, have long been recognized as being unable to satisfy two apparently contradictory needs: to convince the voter that the voter's chosen vote has been included in the tally and to prevent the voter from being able to convince others of what that chosen vote was. As an illustrative but hypothetical scenario, suppose each voter were to receive a standard receipt indicating what vote has been counted as a consequence of their voting act. On the one hand, accuracy and integrity of the tally could be verified by each voter in this scenario. But on the other hand, the “secret ballot” principle, which has been widely adopted in public elections at polling places, requires that voters be unable to provide anyone with convincing proof of how they voted, because of the potential for “improper influence” of voters.
Vote selling has historically been a major type of improper influence and continues today, particularly in certain areas. Coercion, such as by groups or family members, is another type of improper influence and also varies regionally. Although many remote voting systems, such as those used for absentee ballots, do not effectively address the problems of improper influence, they tend to be used most freely in places without a tradition of such abuse. (Abstention or participation in voting are generally not considered subject to improper influence, especially in those countries, such as the United States, where who votes is generally a matter of record and often used by parties.) While communication infrastructure such as the Internet can facilitate some improper influence schemes, facility to secretly cast a replacement vote, such as at a polling place, that takes precedence over a remote vote is known in the art to provide some protection against improperly influenced votes.
There are powerful authentication techniques known in the art that could be used to establish the first of the two apparently contradictory requirements with little room for doubt, such as document security, digital signatures and publishing on computer networks. These could provide the integrity of tallies without relying on trust in any “black box” or poll-worker conducted process. But these strong authentication techniques have been ruled out by limitations of the known ways to satisfy the second requirement.
Receipts are known in voting systems, though to the extent that they are acceptable in terms of ballot secrecy they are ineffective in terms of integrity. Some naive proposals simply print full receipts identifying both voter and candidates chosen, potentially satisfying the first requirement but almost completely sacrificing the second. Others have shown the offices voted, but not the particular candidates chosen. Even these may be too revealing, since voting for a particular office under some scenarios can be the subject of improper influence and this is of course in exchange for little if any real integrity. Even without voter ID, such receipts become a kind of bearer instrument for improper influence, for example establishing that a certain contest was not voted. Schemes that request voters to place the machine-generated receipt in a ballot box before leaving can be divided between those in which the content of the box are used for the actual tally and those that only use it for audit or recount. In the former, a voter that has taken the receipt out of the polling place could use it to show others that no vote was cast. In the latter, the receipt could be convincingly shown by the voter (even though its value would diminish in a recount). It has even been suggested that receipts be kept behind glass before they enter a ballot box.
Where proofs are provided over networks, more generally, there are some known approaches to “non-transitive” convincing. One known type of proof that cannot readily be shown to others is the “private proof systems” developed by the present applicant; however, these require that each voter have a private key and corresponding authentically known public key. Another type of non-transferable proof is one that is convincing to those who are able to choose a random challenge; however, challenges could be chosen other than at random, such as by a coercer or vote buyer. Yet another type of proof is where the proof is conducted in a booth; however, in practice the voter would not be able to bring tools from outside, since they could be provided by those seeking improper influence, and can have only limited trust in whatever tools are provided inside the booth. Universally trusted hardware devices in booths can in principle solve the problems, but themselves pose a very unattractive tradeoff between cost and ability to convince all parties.
Moreover, other shortcomings of various known voting systems are recognized. For example, there are several obvious scenarios allowing a voter to compromise a votes' secrecy or abdicate a vote altogether to persons in the polling place: the authorization the voter has to vote once inside the polling place can be given to and used by another person in the polling place, the voter's freedom in voting can be constrained by voting processes already partially completed by another voter, or evidence of how the voter voted can be revealed to another person within the polling place. A related example is the lack of adequate administrative processes to ensure the proper operation of polling places, including preventing improper allowance or spoiling (canceling) of ballots. Another example is that it may be cumbersome for many different ballot styles to be supported at a polling place, sometimes called “non-geographic” voting, such as for systems with pre-printed ballots, and also the tallies from that place may reveal the votes of voters who are alone in (or among a similarly voting group) using a particular ballot style there. Some systems cannot, after the close of polls, retally by adding or removing the votes of selected voters, such as under court order or for provisional or contested ballots. Some automated systems do not handle write-in ballots in an integrated, privacy protecting and secure manner. Yet other systems require online connection of polling places and/or tamper-proof voting machines.
The present invention aims, among other things, to allow forms of evidence to be removed from the polling place and be verifiable by powerful means and thereby substantially convince the voter of what vote is to be included in the tally, while ensuring that the evidence is in a form that makes it safe against use for improper influence. Objects of the invention also include addressing all the above mentioned concerns including generally providing practical, privacy-protecting, secure, fair, influence-free, robust, verifiable, efficient, low-cost, and flexible voting systems. As an example of flexibility, write-in, non-geographic, offline, and re-tally, are included among objects of the invention for those applications in which they could be beneficial. All manner of apparatus and methods to achieve any and all of the forgoing in voting and in other applications are also included among the objects of the present invention.
Other objects, features, and advantages of the present invention will be appreciated when the present description and appended claims are read in conjunction with the drawing figurers.